import collections

def All(function = None):
    """ Infinite cache decorator """

    class _All(object):
        def __init__(self, function):
            self.function = function
            self.hits     = 0
            self.misses   = 0
            self.data     = {}

        def __call__(self, *key):
            if key not in self.data:
                self.data[key] = self.function(*key)
                self.misses += 1
            else:
                self.hits += 1
            return self.data[key]


        def CacheInfo(self):
            f = self.function.__name__
            s = len(self.mapping)
            h = self.hits
            m = self.misses
            r = 100.0 * h / (h + m)
            print '{0} cache info: Size={1}, Hit={2}, Misses={3}, Ratio={4}%'.format(f, s, h, m, r)

    if function:
        return _All(function)
    return _All


def LruCache(function = None, maxsize = 256):
    """ Least Recently Used cache decorator """

    class _LruCache(object):
        def __init__(self, function):
            self.function = function
            self.hits     = 0
            self.misses   = 0

            PREV, NEXT = 0, 1
            # Node structure [PREV, NEXT, KEY, VALUE]
            self.root = [None, None, None, None]
            self.root[PREV] = self.root[NEXT] = self.root
            self.mapping  = {}
            self.maxsize  = max(maxsize, 1)

        def __call__(self, *key):
            PREV, NEXT = 0, 1
            # Retrieve key value from cache
            node = self.mapping.get(key)

            if node is not None:
                # Cache hit (Put node at the end of the list)
                node_prev, node_next, key, value = node

                # before: node_prev -> node -> node_next
                # after : node_prev -> node_next
                node_prev[NEXT] = node_next
                node_next[PREV] = node_prev

                # before: last -> root
                # after : last -> node -> root
                last = self.root[PREV]
                last[NEXT] = self.root[PREV] = node
                node[PREV] = last
                node[NEXT] = self.root

                # Update stat
                self.hits += 1
            else:
                # Cache miss (Add node at the end of the list)
                value = self.function(*key)

                # Remove last used entry if cache is full
                if len(self.mapping) >= self.maxsize:
                    # before: old_prev -> old -> old_next
                    # after : old_prev -> old_next
                    old_prev, old_next, old_key, old_value = self.root[NEXT]
                    old_prev[NEXT] = old_next
                    old_next[PREV] = old_prev
                    del self.mapping[old_key]

                # before: last -> root
                # after : last -> node -> root
                last = self.root[PREV]
                last[NEXT] = self.root[PREV] = self.mapping[key] = [last, self.root, key, value]

                # Update stat
                self.misses += 1

            return value


        def CacheInfo(self):
            f = self.function.__name__
            s = len(self.mapping)
            h = self.hits
            m = self.misses
            r = 100.0 * h / (h + m)
            print '{0} cache info: Size={1}, Hit={2}, Misses={3}, Ratio={4}%'.format(f, s, h, m, r)

    if function:
        return _LruCache(function)
    return _LruCache

